import bean.TreeNode;

import java.util.ArrayDeque;
import java.util.Queue;

public class LeetCode104 {
    public static void main(String[] args) {

    }

    /**
     * 深度优先-递归
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        int result = 0;
        if (root == null){
            return result;
        }

        result = Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;

        return result;
    }

    /**
     * 广度优先
     * @param root
     * @return
     */
    public int maxDepth1(TreeNode root) {
        int result = 0;
        if (root == null){
            return result;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        // 直到遍历完所有节点，结束遍历，得到层数
        while (!queue.isEmpty()){
            int size = queue.size();

            // 当前树在这里进行上一层的出列，和当前层的入列
            while (size > 0){
                // 出列
                TreeNode node = queue.poll();

                if (node.left != null){
                    queue.offer(node.left);
                }

                if (node.right != null){
                    queue.offer(node.right);
                }

                size--;
            }

            result++;
        }

        return result;
    }
}
